package cn.fxzhang.leetcode.interview;

/**
 * 面试题 17.21. 直方图的水量
 * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 *
 * 类型：枚举
 * 题解：枚举起点，向右找到右边界
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 1 ms, 击败了99.90%
 * 内存消耗: 38.1 MB, 击败了60.94%
 *
 * 【困难】通过次数20,313提交次数32,011
 * todo 本题还有O(N)的解法
 * @author 张晓帆
 * @date 2021/4/2
 */
public class I1721_Volume_Of_Histogram_Lcci {

    public int trap(int[] height) {
        if (height.length <= 2){
            return 0;
        }
        int n = height.length;
        // 辅助数组， 计算累计和
        int[] sum = new int[height.length];
        sum[0] = height[0];
        for (int i=1; i<n; i++){
            sum[i] = sum[i-1] + height[i];
        }

        int i = 0;
        int result = 0;
        while (i < n-1){
            if (height[i+1] > height[i]){
                i++;
                continue;
            }
            // 右边不大于当前高度，并且最大的高度
            int j = i+1;
            for (int k=i+2; k<n; k++){
                if (height[k] > height[j]){
                    j = k;
                }
                if (height[k] >= height[i]){
                    break;
                }
            }
            result += Math.min(height[i], height[j])*(j-i-1)-(sum[j-1]-sum[i]);
            i = j;
        }
        return result;
    }
}
